package Array.easy;

/**
 * 1. 问题描述
 *      给你一个严格升序排列的正整数数组arr和一个整数k 。
 *      请你找到这个数组里第k个缺失的正整数。
 *
 * 2，算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 找到数组中缺省的第k个元素 {

    /**
     * 线性扫描法：缺省元素 = 当前元素 + 剩余差值元素
     * 时间复杂度为O(n), 空间O(1)
     * 代码缺点：边界条件过多，代码有点复杂，不够精简，代码的编写上容易出错
     * @param arr
     * @param k
     * @return
     */
    public int findKthPositive1(int[] arr, int k) {
        int n = arr.length;
        if(n == 1) {
            // 如果当前数组中只有一个元素
            // arr[0] - 1是当前唯一元素之前的缺省元素的个数
            // k - (arr[0] - 1)是当前唯一元素之后缺省的元素个数
            return (k - arr[0] + 1 > 0) ? arr[0] + k - (arr[0] - 1) : k;
        }
        // 下面考虑数组元素大于等于2的情况
        int diff = (arr[0] == 1) ? 0 : arr[0] - 1; // 初始化diff为首元素之前缺省的元素个数
        if(diff > 0 && diff >= k) {
            return k;
        }
        for(int i = 1; i < n; i++) {
            int cur = arr[i] - arr[i-1] - 1; // 记录当前的差值
            if(cur >= 1) { // 只有差值当前差值大于等于2的情况之间才会存在缺省的整数，此时需要更新diff
                // 实际上我们所求的是缺省的元素在数组arr中的那个区间之间，即找到区间的起始索引即可
                // 则缺省的元素就是起始元素+剩余的差值
                // 在更新diff之前，我们就需要判断当前的diff是否满足
                // cur表示当前的差值，k-diff表示剩余的差值
                // 如果剩余的差值小于等于当前差值，表明缺省的元素在当前元素组成的区间之内
                if(k - diff <= cur) {
                    return arr[i-1] + k - diff;  // 注意此时是从i-1开始的，因为更新是在判断之后
                }
                diff += cur;
            }
        }
        // 还有一种可能就扫描完arr之后，没有找到满足的区间，则缺省的元素就是arr最后一个元素之后
        return arr[n-1] + k - diff;
    }

    /**
     * 优化上述代码
     * 由于所谓的缺省的元素是指：1,2,3,4,....., 中，给定数组中缺省的那些元素中第k个缺省的
     * 我们很容易看出，一个没有缺省元素的数组(从1开始，元素之间的差值为1)，其元素和索引的关
     * 系为arr[i] = i + 1,一旦数组存在缺省，则这个索引关系就被破坏了，arr[i] > i+1(只能大于)
     * 此时将arr[i]移动到正确的位置上需要arr[i] - i - 1次，说明之间相差arr[i]-i-1个元素
     * @param arr
     * @param k
     * @return
     */
    public int findKthPositive2(int[] arr, int k) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (arr[i]-i-1 >= k) {
                return k + i;
            }
        }
        return k + n;
    }
}
